home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
HPAVC
/
HPAVC CD-ROM.iso
/
BG_SRC.ZIP
/
BG_EVAL.C
< prev
next >
Wrap
C/C++ Source or Header
|
1995-03-26
|
23KB
|
768 lines
/*
* B G _ E V A L . C -- this file deals with evaulating the 'goodness'
* of a backgammon situation by looking at the layouts and working
* out various values based on characteristics of the layouts. The
* weighted sum of these values is the 'goodness' of a particular
* layout for a particular player.
*
* O.F.Ransen, 14th May 1994
*/
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <conio.h>
#include "bg.h"
/*************************************************************************/
/***** Functions which look at particulars of the current situation *****/
/***** All of these functions should return a number 0..100 *************/
static long Runners_Score (Layout_t Me, Layout_t Him) ;
static long Safety_Score (Layout_t Me, Layout_t Him) ;
static long Tense_Aggro_Score (Layout_t Me, Layout_t Him) ;
static long Wall_Score (Layout_t Me, Layout_t Him) ;
static long Inner_Sec_Score (Layout_t Me, Layout_t Him) ;
static long Outer_Sec_Score (Layout_t Me, Layout_t Him) ;
static long Run_Sec_Score (Layout_t Me, Layout_t Him) ;
static long Mid_Sec_Score (Layout_t Me, Layout_t Him) ;
static long Agro_Coward_Score (Layout_t Me, Layout_t Him) ;
static long Prime_Score (Layout_t Me, Layout_t Him);
static long Entering_IT_Score (Layout_t Me) ;
static long Exiting_Score (Layout_t Me, Layout_t Him) ;
static short Get_Probs (Layout_t Me, Layout_t Him, short My_Pnt) ;
static short Get_Hit_Prob (Layout_t Me, Layout_t Him, short My_Pnt, Dice_t* Dc) ;
static long Constructor_Score (Layout_t Me, Layout_t Him) ;
/*************************************************************************/
static long Runners_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a value based on my last piece.
*/
{
long p,Score ;
p = 0 ;
while ((Me[p] == 0) && (p < HOME_I)) {
p++ ;
}
Score = (p*100)/(N_PLACES-1) ;
return (Score) ;
}
/*************************************************************************/
static long Safety_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a value showing how 'safe' the situation is.
NOTES: 1) If he has more than one piece on the bar and I have no uncovered
pieces in my inner table then I am 100% safe.
2) If he has at least one piece on the bar and I have a 6 piece
wall in my inner table then I am 100% safe.
3) If there is no overlap then I am 100% safe.
*/
{
#define TREMBLE 4 /* Start to get scared when prob >= (TREMBLE/36) */
short p ;
long Uncovered,Score ;
if ((Him[BAR_I] > 1) && (Inner_Sec_Score(Me,Him) == 100l)) {
Score = 100l ;
} else if ((Him[BAR_I] > 0) && (Wall_Score (Me,Him) == 100l)) {
Score = 100l ;
} else if (!Overlap(Me,Him)) {
Score = 100l ;
} else {
/* Rather more complicated... */
Uncovered = 0 ;
for (p = POINT1_I ; p <= POINT24_I ; p++) {
if (Me[p] == 1) {
if (Get_Probs (Me,Him,p) >= TREMBLE) {
Uncovered++ ;
}
}
}
if (Uncovered > (long)MAX_MOVES) {
Uncovered = (long)MAX_MOVES ;
}
Score= (long)((((long)MAX_MOVES-Uncovered)*100)/(long)MAX_MOVES) ;
}
return (Score) ;
}
/*************************************************************************/
#if DRODBAR
long Weighted_Safety (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on the 'safeness' of the exposed
pieces. We look at each single piece and calculate the probabilty
that it will be hit by the next throw of the opponents dice. We
add the probablilities up and return a number based on that.
*/
{
long Total = 0, Prob ;
short p ;
/* For every uncovered point... */
for (p = 1 ; p < HOME_I ; p++) {
if (Me[p] == 1) {
Prob = (long)Get_Probs (Me,Him,p,TRUE) ;
Total = Total + Prob ;
}
}
return (Total) ;
}
#endif
/*************************************************************************/
static long Tense_Aggro_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To balance the number of pieces I have eaten with the number
of exposed pieces in his inner table. The score is high when
I eat a lot and he has lots of exposed pieces.
*/
{
const long Max_Exposed = 6 ;
const long Max_Eaten = 4 ;
long Exposed, Eaten, Score ;
short p;
Exposed = 0 ;
for (p = 19 ; p <= 24 ; p++) {
if (Him[p] == 1) {
Exposed++ ;
}
}
Eaten = Him[BAR_I] ;
Score = ((Exposed*100)/Max_Exposed) * ((Eaten*100)/Max_Eaten) ;
return (Score/100) ;
}
/*************************************************************************/
long Aggression_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a value showing how many pieces have been eaten by me.
NOTES: 1) Used in this file, but also in BG_FACE.C to draw the teeth!
*/
{
long Eaten ;
Eaten = Him[BAR_I] ;
if (Eaten > (long)MAX_MOVES) { /* Rare, so limit it's importance */
Eaten = (long)MAX_MOVES ;
}
return ((Eaten*100l)/(long)MAX_MOVES) ;
}
/*************************************************************************/
static long Wall_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on how much of a wall I have built in
*/
{
const short Max_Wall_Score = 6 ;
long Score ;
short p ;
Score = 0 ;
for (p = 19 ; p <= POINT24_I ; p++) {
if (Me[p] > 1) {
Score++ ;
}
}
return ((Score*100)/Max_Wall_Score) ;
}
/*************************************************************************/
static long Inner_Sec_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on how few of my pieces are
uncovered in my inner table.
*/
{
long const Max_Uncovered = 6 ;
long Uncovered ;
short p ;
Uncovered = 0 ;
for (p = 19 ; p <= 24 ; p++) {
if (Me[p] == 1) {
Uncovered++ ;
}
}
return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
}
/*************************************************************************/
static long Outer_Sec_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on how few pieces are uncovered
in my outer table.
*/
{
long const Max_Uncovered = 6 ;
long Uncovered ;
short p ;
Uncovered = 0 ;
for (p = 13 ; p <= 18 ; p++) {
if (Me[p] == 1) {
Uncovered++ ;
}
}
return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
}
/*************************************************************************/
static long Run_Sec_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on how few of my pieces are uncovered
in his inner table.
*/
{
long const Max_Uncovered = 6 ;
long Uncovered ;
short p ;
Uncovered = 0 ;
for (p = 1 ; p <= 6 ; p++) {
if (Me[p] == 1) {
Uncovered++ ;
}
}
return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
}
/*************************************************************************/
static long Mid_Sec_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on how few of my pieces are uncovered
in his outer table.
*/
{
long const Max_Uncovered = 6 ;
long Uncovered ;
short p ;
Uncovered = 0 ;
for (p = 7 ; p <= 12 ; p++) {
if (Me[p] == 1) {
Uncovered++ ;
}
}
return (((Max_Uncovered-Uncovered)*100)/Max_Uncovered) ;
}
/*************************************************************************/
static long Agro_Coward_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on how many I can eat without risk.
*/
{
short p ;
for (p = 19 ; p <= POINT24_I ; p++) {
if (Me[p] == 1) {
return (0) ;
}
}
/* No uncovered pieces in home area, I can eat */
return (Aggression_Score(Me,Him)) ;
}
/*************************************************************************/
static long Prime_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on the longest run of occupied points
*/
{
#define MAX_PRIME 6
long P_Count,Max_Found ;
short p ;
if (!Overlap (Me,Him)) {
return (0l) ;
}
P_Count = 0 ;
Max_Found = 0 ;
for (p = 15 ; p < 22 ; p++) {
if (Me[p] > 1) {
P_Count++ ;
if (P_Count > Max_Found) {
Max_Found = P_Count ;
}
} else {
P_Count=0 ;
}
}
if (Max_Found >= MAX_PRIME) {
return (100l) ;
} else {
return ((Max_Found*100l)/MAX_PRIME) ;
}
}
/*************************************************************************/
#define MAX_ENTERING_SCORE 49 /* These two defines force exiting... */
#define MIN_EXITING_SCORE 51 /* ...to always win over entering... */
static long Entering_IT_Score (Layout_t Me)
/*
PURPOSE: To return a value based on getting into my inner table.
NOTES: 1) This is rather hand-crafted...
*/
{
#define FIRST_IT_POINT 19 /* Just inside the bar */
#define MAX_END_PIECES 1
long p,Score,N_End_Pieces ;
p = BAR_I ;
while ((Me[p] == 0) && (p < FIRST_IT_POINT)) {
p++ ;
}
if (p >= FIRST_IT_POINT) {
Error_Exit ("Entering score when bearing off!") ;
}
N_End_Pieces = Me[p] ;
if (N_End_Pieces > 1) {
/*
* There is a column to be shifted, return a very low score
*/
if (N_End_Pieces > MAX_END_PIECES) {
N_End_Pieces = MAX_END_PIECES ;
}
Score = MAX_END_PIECES - N_End_Pieces ;
} else {
/*
* There is just a single trailing piece
*/
Score = (p*MAX_ENTERING_SCORE)/(FIRST_IT_POINT-1) ;
}
return (Score) ;
}
/*************************************************************************/
static long Exiting_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a number based how many pieces I have taken off
the board or how close I have got to taking them off
*/
{
long Score ;
Score = (Me[HOME_I]*(100l-MIN_EXITING_SCORE))/(long)N_PIECES ;
Score = Score + MIN_EXITING_SCORE ;
return (Score);
}
/*************************************************************************/
static short Get_Probs (Layout_t Me, Layout_t Him, short My_Point)
/*
PURPOSE: To return a number (0..36 inclusive) which gives the
probability that the point will be hit by the opponent.
*/
{
Dice_t Dice ;
short Total,d0,d1,i,Loc_Tot ;
Total = 0 ;
for (d0 = 1 ; d0 <= 6 ; d0++) {
for (d1 = 1 ; d1 <= 6 ; d1++) {
if (d1 == d0) {
Dice.N_Vals = 4 ;
for (i = 0 ; i < 4 ; i++) {
Dice.Values[i] = (char)d0 ;
}
} else {
Dice.N_Vals = 2 ;
Dice.Values[0] = (char)d0 ;
Dice.Values[1] = (char)d1 ;
}
Loc_Tot = Get_Hit_Prob (Me,Him,My_Point,&Dice) ;
Total = Total + Loc_Tot ;
}
}
return (Total) ;
}
/*************************************************************************/
static short Get_Hit_Prob (Layout_t Me, Layout_t Him, short My_Point, Dice_t* Dice)
/*
PURPOSE: To return 0 if the piece cannot be hit with the Dice, or
1 if it can be hit.
*/
{
short His_Point,His_Start,Mine,i,d0,d1 ;
short Long_Point,Mediate_Point0,Mediate_Point1 ;
if (Me[My_Point] != 1) {
return (0) ;
}
His_Point = Reverse_Index (My_Point) ;
d0 = Dice->Values[0] ;
d1 = Dice->Values[1] ;
if (Dice->N_Vals == 4) {
/* Hit via double */
for (i = 1 ; i <= 4 ; i++) {
His_Start = His_Point - (d0*i) ; /* Where he starts from */
Mine = Reverse_Index (His_Start) ;
if (His_Start < BAR_I) {
return (0) ; /* He can't be at less than the bar point */
} else if (Me[Mine] > 1) {
return (0) ; /* I occupy that point */
} else if (Him[His_Start] > 0) {
return (1) ; /* He could get me with that piece */
}
}
return (0) ;
} else {
/* Check for direct hit with first dice... */
His_Start = His_Point - d0 ;
if (His_Start >= BAR_I) {
if (Him[His_Start] > 0) {
return (1) ;
}
}
/* Check for direct hit with second dice... */
His_Start = His_Point - d1 ;
if (His_Start >= BAR_I) {
if (Him[His_Point-d1] > 0) {
return (1) ;
}
}
/* Check for an indirect hit... */
Long_Point = His_Point - (d0 + d1) ;
if (Long_Point < BAR_I) {
return (0) ;
} else if (Him[Long_Point] == 0) {
return (0) ;
} else {
Mediate_Point0 = Reverse_Index (His_Point - d0) ;
Mediate_Point1 = Reverse_Index (His_Point - d1) ;
if ((Me[Mediate_Point0] > 1) && (Me[Mediate_Point1] > 1)) {
return (0) ; /* I block indirect hit */
} else {
return (1) ; /* No blockage */
}
}
}
}
/*************************************************************************/
boolean Overlap (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return TRUE if there are any of his pieces in front of any
of mine.
*/
{
short p, My_Last ;
My_Last = HOME_I ; /* Optimistic */
for (p = HOME_I ; p >= BAR_I ; p--) {
if (Me[p] != 0) {
My_Last = p ;
}
}
p = Reverse_Index (My_Last) ;
while (p >= BAR_I) {
if (Him[p] != 0) {
return (TRUE) ;
}
p-- ;
}
return (FALSE) ;
}
/***************************************************************************/
short Pip_Count (Layout_t Layout)
/*
PURPOSE: To return the pip count of this layout
NOTES: Smaller numbers are better, means less pieces far away.
*/
{
short p,P_Count ;
P_Count = 0 ;
for (p = BAR_I ; p <= HOME_I ; p++) {
P_Count = P_Count + ((HOME_I-p)*Layout[p]) ;
}
if (P_Count < 0) {
Error_Exit ("P_Count < 0") ;
}
return (P_Count) ;
}
/*************************************************************************/
short Pip_Count_Diff (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a number showing the 'advantage' one player has over
the other. If the number is negative He has the advantage, if
the number is positive I have the advantage.
*/
{
short Mine,His ;
Mine = Pip_Count (Me) ;
His = Pip_Count (Him) ;
return (His - Mine) ;
}
/*************************************************************************/
long Pip_Count_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on the pip count.
*/
{
const long Worst_Pips = -375l ;
const long Pips_Range = (375l*2l) ;
long Pips,Score ;
Pips = (long)Pip_Count_Diff (Me,Him) ;
Score = ((Pips - Worst_Pips)*100l)/Pips_Range ;
return (Score) ;
}
/*************************************************************************/
short Total_Pieces_On_Board (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return the number of pieces left on the board.
*/
{
short Mine,His ;
Mine = Pieces_On_Board (Me) ;
His = Pieces_On_Board (Him) ;
return (Mine + His) ;
}
/*************************************************************************/
short Pieces_On_Board (Layout_t Layout)
/*
PURPOSE: To return the number of pieces left on the board in My layout
*/
{
short Pieces ;
Pieces = 15 - Layout[HOME_I] ;
return (Pieces) ;
}
/*************************************************************************/
static long Constructor_Score (Layout_t Me, Layout_t Him)
/*
PURPOSE: To return a score based on the number of constructors in
my outer table.
*/
{
#define QUARTER 9 /* 9/36 = a quarter no? */
long Count,Danger ;
short p ;
/*
* See if we have the basis for construction...
*/
if (Me[19] < 3) {
return (0l) ;
}
if (!((Me[18] > 2) || (Me[17] > 2))) {
return (0l) ;
}
/*
* If we get here we have a fullish bar point and a fattish
* pre-bar point too. Now see how many single constructors
* there are...
*/
Count = 0 ;
Danger = 0 ;
for (p = 14 ; p <= 16 ; p++) {
if (Me[p] == 1) {
Danger = Danger + Get_Probs (Me,Him,p) ;
Count++ ;
}
}
if (Count > 0) {
if ((Danger/Count) > QUARTER) {
Count = 0 ;
}
}
return ((Count*100l)/3l) ;
}
/*************************************************************************/
/* The W_Func_t, holds the function, the name of the function (in
many languages), and the weight for the function for both players. */
typedef struct {
long (*W_Func)(Layout_t,Layout_t) ; /* Type of function */
long Weight [N_PLAYERS] ; /* Weights for each player */
long Min,Max ; /* For later analysis */
char Name [32] ; /* For later analysis */
} W_Func_t ;
static W_Func_t W_F_Table [N_WEIGHTS] = {
/* Function, weight min max id */
{Runners_Score, {0,0}, 200,-200,"Runners " },
{Prime_Score, {0,0}, 200,-200,"Prime " },
{Safety_Score, {0,0}, 200,-200,"Safety " },
{Aggression_Score, {0,0}, 200,-200,"Aggro " },
{Tense_Aggro_Score, {0,0}, 200,-200,"Tense Aggro " },
{Wall_Score, {0,0}, 200,-200,"Wall " },
{Agro_Coward_Score, {0,0}, 200,-200,"Agro Coward " },
{Inner_Sec_Score, {0,0}, 200,-200,"Inr Sec " },
{Outer_Sec_Score, {0,0}, 200,-200,"Outr Sec " },
{Run_Sec_Score, {0,0}, 200,-200,"Run Sec " },
{Mid_Sec_Score, {0,0}, 200,-200,"Mid Sec " },
{Pip_Count_Score, {0,0}, 200,-200,"Pip Score " },
{Constructor_Score, {0,0}, 200,-200,"Constructor " }
} ;
/*************************************************************************/
/* See BG_USER1.C and BG.H for names of opponents */
long Weights [N_OPPS][N_WEIGHTS] = {
/*runrs pri safe aggro tenagr wall agrwal innr outr runsec midsec pips cons */
{ 73, 0, 23, 50, 79, 35, 50, 100, 25, 60, 75, 75, 16}, // Sergio
{ 36, 50, 24, 76, 48, 20, 44, 46, 50, 40, 5, 64, 58}, // Enzo
{ 58, 10, 38, 85, 54, 70, 45, 70, 70, 35, 70, 60, 0}, // Owen
{ 51, 65, 59, 51, 10, 25, 10, 51, 90, 35, 15, 69, 10}, // Brian
} ;
static short Curr_Opponent = SERGIO ;
void Setup_Weights (short New_Opponent, Player_t Player)
/*
PURPOSE: To copy the opponents weights into the W_F_Table.
The Player will be black or white, and we must copy
the opponents weights into the black or white list
of weights. The list of weights of the human (white or
black) are set to 0 to speed up evaluation.
*/
{
short w ;
for (w = 0 ; w < N_WEIGHTS ; w++) {
W_F_Table[w].Weight[Player] = Weights[New_Opponent][w] ;
W_F_Table[w].Weight[OPPONENT(Player)] = 0 ;
}
if (Curr_Opponent != New_Opponent) {
Init_Stats () ;
Curr_Opponent = New_Opponent ;
}
}
/*************************************************************************/
static short Curr_Black_Id = SERGIO ;
static short Curr_White_Id = ENZO ;
void Init_Genetic_Opponents (short Black, short White)
/*
PURPOSE: To set the black players weights to the values in
Weights[BLACK], and the white players weights to the values in
Weights[WHITE].
*/
{
short w ;
for (w = 0 ; w < N_WEIGHTS ; w++) {
W_F_Table[w].Weight[BLACK_PLAYER] = Weights[Black][w] ;
W_F_Table[w].Weight[WHITE_PLAYER] = Weights[White][w] ;
}
Curr_Black_Id = Black ;
Curr_White_Id = White ;
}
/*************************************************************************/
long Evaluate_Move (Layout_t Me, Layout_t Him, Player_t Player)
/*
PURPOSE: To return the weighted sum for this player and his situation.
*/
{
long Score,Temp ;
extern boolean Debugging,Genetics ;
ushort w ;
if (!Overlap(Me,Him)) {
/* The choice of move is rather simple, we are just racing */
if (!Bearing_Off(Me)) {
Score = Entering_IT_Score (Me) ; /* Move closer to inner table */
} else {
Score = Exiting_Score (Me,Him) ; /* Take pieces off inner table */
}
return (Score) ;
}
// Using normal statistics methods, not the NN brain
Score = 0 ;
for (w = 0 ; w < N_WEIGHTS ; w++) {
/* Get the value for this weight */
Temp = (*W_F_Table[w].W_Func) (Me,Him) ;
/* Check the value is not illegal */
if (Temp < 0) {
printf ("\nAn evaluation score = %ld, w=%d, <%s>.",Temp,w,W_F_Table[w].Name) ;
Error_Exit ("A negative evaluation score") ;
} else if (Temp > 100) {
printf ("\nAn evaluation score = %ld, w=%d,<%s>.",Temp,w,W_F_Table[w].Name) ;
Error_Exit ("An evaluation greater than 100") ;
}
/* Record the excursions of the weight for later analysis */
if (Temp > W_F_Table[w].Max) {
W_F_Table[w].Max = Temp ;
}
if (Temp < W_F_Table[w].Min) {
W_F_Table[w].Min = Temp ;
}
/* Add the value into the score */
Score = Score + (W_F_Table[w].Weight[Player]*Temp) ;
}
return (Score) ;
}
/*************************************************************************/